{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #First Common Ancestor LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lowestCommonAncestor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #首个共同祖先"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。</p>\n",
    "\n",
    "<p>例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]</p>\n",
    "\n",
    "<pre>    3\n",
    "   / \\\n",
    "  5   1\n",
    " / \\ / \\\n",
    "6  2 0  8\n",
    "  / \\\n",
    " 7   4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 节点 5 和节点 1 的最近公共祖先是节点 3。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4\n",
    "<strong>输出:</strong> 5\n",
    "<strong>解释:</strong> 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。</pre>\n",
    "\n",
    "<p><strong>说明:</strong></p>\n",
    "\n",
    "<pre>所有节点的值都是唯一的。\n",
    "p、q 为不同节点且均存在于给定的二叉树中。</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [first-common-ancestor-lcci](https://leetcode.cn/problems/first-common-ancestor-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [first-common-ancestor-lcci](https://leetcode.cn/problems/first-common-ancestor-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if root in (None, p, q):\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        return left if left else right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        def dfs(node,dpt):\n",
    "            if not node:\n",
    "                return False,False\n",
    "            pp = False\n",
    "            qq = False \n",
    "            if node is p:\n",
    "                pp = True \n",
    "            if node is q:\n",
    "                qq = True\n",
    "            pl,ql = dfs(node.left,dpt+1)\n",
    "            pr,qr = dfs(node.right,dpt+1)\n",
    "            pp = pp or pl or pr\n",
    "            qq = qq or ql or qr\n",
    "            if pp and qq and cur[1]<dpt:\n",
    "                cur[0],cur[1]=node,dpt\n",
    "            return pp,qq\n",
    "        \n",
    "        cur = [None,-1]\n",
    "        dfs(root,1)\n",
    "        return cur[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root.val == p.val or root.val == q.val:\n",
    "            return root\n",
    "        left =self.lowestCommonAncestor(root.left,p,q)\n",
    "        right =self.lowestCommonAncestor(root.right,p,q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        return left if left else  right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root == p or root == q:\n",
    "            return root\n",
    "\n",
    "        root.left = self.lowestCommonAncestor(root.left,p,q)\n",
    "        root.right = self.lowestCommonAncestor(root.right,p,q)\n",
    "\n",
    "        if root.left and root.right:\n",
    "            return root\n",
    "        elif root.left and root.right == None:\n",
    "            return root.left\n",
    "        elif root.left == None and root.right:\n",
    "            return root.right\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def find_node(root, p, q):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root == p or root == q:\n",
    "                return root\n",
    "            left = find_node(root.left, p, q)\n",
    "            right = find_node(root.right, p, q)\n",
    "            if left and right:\n",
    "                return root\n",
    "            elif left and not right:\n",
    "                return left\n",
    "            elif right and not left:\n",
    "                return right\n",
    "        ans = find_node(root, p, q)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':\n",
    "\n",
    "        if not root or root == p or root == q: \n",
    "            return root\n",
    "        \n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        if not left: \n",
    "            return right\n",
    "        if not right: \n",
    "            return left\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "# 作者：Krahets\n",
    "# 链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solutions/240096/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        def dfs(root,p,q):\n",
    "            if not root or root == p or root == q:\n",
    "                return root\n",
    "            l = dfs(root.left,p,q)\n",
    "            r = dfs(root.right,p,q)\n",
    "            if l and r:\n",
    "                return root\n",
    "            elif l :\n",
    "                return l\n",
    "            elif r:\n",
    "                return r\n",
    "                \n",
    "        return dfs(root,p,q)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        def helper(node):\n",
    "            if not node.left and not node.right:\n",
    "                if node == p or node == q:\n",
    "                    return 1, node\n",
    "                else:\n",
    "                    return 0, None\n",
    "            cur = 1 if node in [p, q] else 0\n",
    "            if node.left:\n",
    "                lf, ln = helper(node.left)\n",
    "                if lf == 2:\n",
    "                    return lf, ln\n",
    "                cur += lf\n",
    "            if node.right:\n",
    "                rf, rn = helper(node.right)\n",
    "                if rf == 2:\n",
    "                    return rf, rn\n",
    "                cur += rf\n",
    "\n",
    "            return cur, node\n",
    "            \n",
    "        return helper(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root.val == p.val or root.val == q.val:\n",
    "            return root\n",
    "        left =self.lowestCommonAncestor(root.left,p,q)\n",
    "        right =self.lowestCommonAncestor(root.right,p,q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        return left if left else  right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        res = None\n",
    "\n",
    "        def dfs(root: TreeNode) -> bool:\n",
    "            nonlocal res\n",
    "            if root is None:\n",
    "                return False\n",
    "            state = dfs(root.left) + dfs(root.right) + (root is p) + (root is q)\n",
    "            if state == 2:\n",
    "                res = root\n",
    "            return state != 0\n",
    "\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root==q or root==p:\n",
    "            return root\n",
    "        left=self.lowestCommonAncestor(root.left,p,q)\n",
    "        right=self.lowestCommonAncestor(root.right,p,q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        if not left:\n",
    "            return right\n",
    "        else:\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.father_map = {}\n",
    "        self.depth_map = {}\n",
    "        self.dfs(root, 0)\n",
    "        if self.depth_map[p.val] < self.depth_map[q.val]:\n",
    "            p, q = q, p\n",
    "        diff_depth = self.depth_map[p.val] - self.depth_map[q.val]\n",
    "        # p_value = p.val\n",
    "        # q_value = q.val\n",
    "        for i in range(diff_depth):\n",
    "            p = self.father_map[p]\n",
    "        while p.val != q.val:\n",
    "            p = self.father_map[p]\n",
    "            q = self.father_map[q]\n",
    "        return p\n",
    "\n",
    "    \n",
    "\n",
    "    def dfs(self, node, depth):\n",
    "        if not node:\n",
    "            return\n",
    "        self.depth_map[node.val] = depth\n",
    "        if node.left:\n",
    "            self.father_map[node.left] = node\n",
    "            self.dfs(node.left, depth + 1)\n",
    "        if node.right:\n",
    "            self.father_map[node.right] = node\n",
    "            self.dfs(node.right, depth + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "       if root in (p, q, None):\n",
    "          return root\n",
    "       left = self.lowestCommonAncestor(root.left, p, q)\n",
    "       right = self.lowestCommonAncestor(root.right, p, q)\n",
    "       if left and right:\n",
    "         return root\n",
    "       return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        res = None\n",
    "\n",
    "        def dfs(root: TreeNode) -> int:\n",
    "            nonlocal res\n",
    "            if root is None:\n",
    "                return 0\n",
    "            state = dfs(root.left) | dfs(root.right)\n",
    "            if root is p:\n",
    "                state |= 2\n",
    "            elif root is q:\n",
    "                state |= 1\n",
    "            if res is None and state == 3:\n",
    "                res = root\n",
    "            return state\n",
    "\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return\n",
    "        if root is p or root is q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        if left is None:\n",
    "            return right\n",
    "\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root==p or root==q:\n",
    "            return root\n",
    "        left=self.lowestCommonAncestor(root.left,p,q)\n",
    "        right=self.lowestCommonAncestor(root.right,p,q)\n",
    "        if left and right: return root\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.rtn = None\n",
    "        def common(cur):\n",
    "            if not cur: return None\n",
    "            if cur == p or cur == q: return cur\n",
    "            l = None if not cur.left else common(cur.left)\n",
    "            r = None if not cur.right else common(cur.right)\n",
    "            if l and r: return cur\n",
    "            if l: return l \n",
    "            return r \n",
    "        \n",
    "        ans = common(root)\n",
    "        if not ans: return root\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) ->TreeNode:\n",
    "        self.p=p\n",
    "        self.q=q\n",
    "        self.out=None\n",
    "\n",
    "        def lowes(root):\n",
    "            now=0\n",
    "\n",
    "            if not root:\n",
    "                return 0\n",
    "            elif root==self.p or root==self.q:\n",
    "                now= 1\n",
    "\n",
    "            if (left:=lowes(root.left))==2:\n",
    "                return 2\n",
    "            if (right:=lowes(root.right))==2:\n",
    "                return 2\n",
    "\n",
    "            now+=left+right\n",
    "            \n",
    "            if now==2:\n",
    "                self.out=root\n",
    "\n",
    "            return now\n",
    "\n",
    "\n",
    "        lowes(root)\n",
    "        return self.out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "\n",
    "        if root in (None,p,q):\n",
    "            return root\n",
    "       \n",
    "        left = self.lowestCommonAncestor(root.left,p,q)\n",
    "        right = self.lowestCommonAncestor(root.right,p,q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        if left:\n",
    "            return left\n",
    "        else:\n",
    "            return right\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        # 当 root 为空或者 root 等于 p 或者 root 等于 q 时，返回 root\n",
    "        if root in(None,p,q):\n",
    "            return root\n",
    "\n",
    "        # 在左子树中查找 p 和 q 的最近公共祖先\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        # 在右子树中查找 p 和 q 的最近公共祖先\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        # 如果左子树和右子树都找到了公共祖先，说明当前节点 root 就是最近公共祖先\n",
    "        if left and right:\n",
    "            return root\n",
    "\n",
    "        # 返回左子树或右子树中找到的公共祖先，如果左子树中没有找到，返回右子树中的公共祖先，反之亦然\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if root in (None, p, q):\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        return left if left else right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        def recur(root, p, q):\n",
    "            if not root or root == p or root == q:\n",
    "                return root\n",
    "            \n",
    "            left = recur(root.left, p, q)\n",
    "            right = recur(root.right, p, q)\n",
    "\n",
    "            if not left:\n",
    "                return right\n",
    "            if not right:\n",
    "                return left\n",
    "            return root\n",
    "        \n",
    "        return recur(root, p, q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right: return root\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        RE = [TreeNode()]\n",
    "        def preSearch(root,p,q):\n",
    "            if root is None:\n",
    "                return False\n",
    "            lson = preSearch(root.left,p,q)\n",
    "            rson = preSearch(root.right,p,q)\n",
    "            if (lson and rson) or ((root==p or root==q) and (lson or rson)):\n",
    "                RE[0] = root\n",
    "            return root==p or root==q or lson or rson\n",
    "        preSearch(root,p,q)\n",
    "        return RE[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if root == None or p == root or q == root:\n",
    "            return root\n",
    "\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        # p q, 在 root 节点两边\n",
    "        if left and right:\n",
    "            return root\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        if left:\n",
    "            return left\n",
    "        if right:\n",
    "            return right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        ans = None\n",
    "        def dfs(root, p, q):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return False\n",
    "            lson = dfs(root.left, p, q)\n",
    "            rson = dfs(root.right, p, q)\n",
    "            if (lson and rson) or ((root==p or root==q) and (lson or rson)):\n",
    "                ans = root\n",
    "            return lson or rson or root==p or root==q\n",
    "        dfs(root,p,q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        lnode = self.lowestCommonAncestor(root.left, p, q)\n",
    "        rnode = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if lnode and rnode:\n",
    "            return root\n",
    "        if lnode:\n",
    "            return lnode\n",
    "        if rnode:\n",
    "            return rnode\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(node, p, q):\n",
    "            if node == None:\n",
    "                return None\n",
    "            left_node = dfs(node.left, p, q)\n",
    "            right_node = dfs(node.right, p, q)\n",
    "            if node == p or node == q or (left_node != None and right_node != None):\n",
    "                return node\n",
    "            else:\n",
    "                return left_node or right_node\n",
    "        return dfs(root, p, q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        # 0 都没有， 1有p, 2,有q, 3有pq\n",
    "        def search(node):\n",
    "            if node is None:\n",
    "                return 0, node\n",
    "            \n",
    "            left_s, left_n = search(node.left)\n",
    "            right_s, right_n = search(node.right)\n",
    "            \n",
    "            if left_s == 3:\n",
    "                return 3, left_n\n",
    "            elif right_s == 3:\n",
    "                return 3, right_n\n",
    "            elif (left_s == 1 and right_s == 2) or (left_s == 2 and right_s == 1):\n",
    "                return 3, node\n",
    "            elif (left_s == 1 or right_s == 1) and (node.val == q.val):\n",
    "                return 3, node\n",
    "            elif (left_s == 2 or right_s == 2) and (node.val == p.val):\n",
    "                return 3, node\n",
    "            elif (left_s == 1 and right_s == 0) or (left_s == 0 and right_s == 1) or (node.val == p.val):\n",
    "                return 1, node\n",
    "            elif (left_s == 2 and right_s == 0) or (left_s == 0 and right_s == 2) or (node.val == q.val):\n",
    "                return 2, node\n",
    "            else:\n",
    "                return 0, node\n",
    "        s, n = search(root)\n",
    "        # print(s, n.val)\n",
    "        return n if s == 3 else None\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ancestor = None\n",
    "\n",
    "    def have(self, root, node):\n",
    "        if (root is None):\n",
    "            return False\n",
    "        if (root == node or self.have(root.left, node) or self.have(root.right, node)):\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if (root is None):\n",
    "            return None\n",
    "        self.lowestCommonAncestor(root.left, p, q)\n",
    "        self.lowestCommonAncestor(root.right, p, q)\n",
    "        if (self.ancestor is None and self.have(root, p) and self.have(root, q)):\n",
    "            self.ancestor = root\n",
    "        return self.ancestor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.rtn = None\n",
    "        def common(cur):\n",
    "            if not cur: return None\n",
    "            if cur == p or cur == q: return cur\n",
    "            l = None if not cur.left else common(cur.left)\n",
    "            r = None if not cur.right else common(cur.right)\n",
    "            if l and r: return cur\n",
    "            if l: return l \n",
    "            return r \n",
    "        \n",
    "        ans = common(root)\n",
    "        # if not ans: return root\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(root, p, q):\n",
    "            if not root:\n",
    "                return False\n",
    "            leftChild = dfs(root.left, p, q)\n",
    "            rightChild = dfs(root.right, p, q)\n",
    "            if leftChild and rightChild or ((root.val == p.val or root.val == q.val) and (leftChild or rightChild)):\n",
    "                nonlocal ans\n",
    "                ans = root \n",
    "            return leftChild or rightChild or (root.val == p.val or root.val == q.val)\n",
    "        ans = None\n",
    "        dfs(root, p, q)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        if not root:\n",
    "            return \n",
    "\n",
    "        if root == q or  root == p:\n",
    "            return root\n",
    "        \n",
    "\n",
    "        left = self.lowestCommonAncestor(root.left,p,q)\n",
    "        right = self.lowestCommonAncestor(root.right,p,q)\n",
    "\n",
    "        if left and right:\n",
    "            return root\n",
    "        if left and not right:\n",
    "            return left\n",
    "        else:\n",
    "            return right\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        # 0 都没有， 1有p, 2,有q, 3有pq\n",
    "        def search(node):\n",
    "            if node is None:\n",
    "                return 0, node\n",
    "            \n",
    "            left_s, left_n = search(node.left)\n",
    "            right_s, right_n = search(node.right)\n",
    "            \n",
    "            if left_s == 3:\n",
    "                return 3, left_n\n",
    "            elif right_s == 3:\n",
    "                return 3, right_n\n",
    "            elif (left_s == 1 and right_s == 2) or (left_s == 2 and right_s == 1):\n",
    "                return 3, node\n",
    "            elif ((left_s == 1 or right_s == 1) and (node.val == q.val)) or ((left_s == 2 or right_s == 2) and (node.val == p.val)) :\n",
    "                return 3, node\n",
    "            # elif (left_s == 2 or right_s == 2) and (node.val == p.val):\n",
    "            #     return 3, node\n",
    "            elif (left_s == 1 and right_s == 0) or (left_s == 0 and right_s == 1) or (node.val == p.val):\n",
    "                return 1, node\n",
    "            elif (left_s == 2 and right_s == 0) or (left_s == 0 and right_s == 2) or (node.val == q.val):\n",
    "                return 2, node\n",
    "            else:\n",
    "                return 0, node\n",
    "        s, n = search(root)\n",
    "        # print(s, n.val)\n",
    "        return n if s == 3 else None\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        ans = None\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "\n",
    "            if root is None:\n",
    "                return False\n",
    "            \n",
    "            isLeft = dfs(root.left)\n",
    "            isRight = dfs(root.right)\n",
    "\n",
    "            if isLeft and isRight:\n",
    "                if ans is None:\n",
    "                    ans = root\n",
    "\n",
    "            if (root == p or root == q) and (isLeft or isRight):\n",
    "                if ans is None:\n",
    "                    ans = root\n",
    "\n",
    "            return isLeft or isRight or root == p or root == q\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        # 当 root 为空或者 root 等于 p 或者 root 等于 q 时，返回 root\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "\n",
    "        # 在左子树中查找 p 和 q 的最近公共祖先\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        # 在右子树中查找 p 和 q 的最近公共祖先\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        # 如果左子树和右子树都找到了公共祖先，说明当前节点 root 就是最近公共祖先\n",
    "        if left and right:\n",
    "            return root\n",
    "\n",
    "        # 返回左子树或右子树中找到的公共祖先，如果左子树中没有找到，返回右子树中的公共祖先，反之亦然\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        path_p = self.find_path(root, p)\n",
    "        path_q = self.find_path(root, q)\n",
    "        p_index, q_index = 0, 0\n",
    "        while p_index < len(path_p) and q_index < len(path_q):\n",
    "            if path_p[p_index].val != path_q[q_index].val:\n",
    "                break\n",
    "            p_index += 1\n",
    "            q_index += 1\n",
    "        return path_p[p_index - 1]\n",
    "\n",
    "    def find_path(self, root: TreeNode, target: TreeNode) -> List[TreeNode]:\n",
    "        if target.val == root.val:\n",
    "            return [root]\n",
    "        if root.left is not None:\n",
    "            left_path = self.find_path(root.left, target)\n",
    "            if left_path is not None:\n",
    "                return [root] + left_path\n",
    "        if root.right is not None:\n",
    "            right_path = self.find_path(root.right, target)\n",
    "            if right_path is not None:\n",
    "                return [root] + right_path\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if root == None or p == root or q == root:\n",
    "            return root\n",
    "\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        if left == None:\n",
    "            return right\n",
    "\n",
    "        if right == None:\n",
    "            return left\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right: return root\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        if p==root or q == root:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        if left and right:\n",
    "            return root\n",
    "        elif left and not right:\n",
    "            return left\n",
    "        else:\n",
    "            return right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        if left:\n",
    "            return left\n",
    "        else:\n",
    "            return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None \n",
    "        if root == q or root == p:\n",
    "            return root \n",
    "        \n",
    "        left_found = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right_found = self.lowestCommonAncestor(root.right, p, q)\n",
    "\n",
    "        if left_found and right_found:\n",
    "            return root \n",
    "        elif left_found and right_found is None:\n",
    "            return left_found\n",
    "        elif right_found and left_found is None:\n",
    "            return right_found\n",
    "        else:\n",
    "            return None "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root==p or root==q:\n",
    "            return root\n",
    "        l, r = self.lowestCommonAncestor(root.left,p,q), self.lowestCommonAncestor(root.right,p,q)\n",
    "        if l and r:\n",
    "            return root\n",
    "        return l if l else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "  \n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if  left and right:\n",
    "            return root\n",
    "        if not left:\n",
    "            return right \n",
    "        if not right:\n",
    "            return left \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        res = root\n",
    "\n",
    "        def isContain(root):\n",
    "            nonlocal res\n",
    "            if root is None:\n",
    "                return False\n",
    "            lc = isContain(root.left)\n",
    "            rc = isContain(root.right)\n",
    "            if (root is p or root is q) and (lc or rc):\n",
    "                res = root\n",
    "                return True\n",
    "            if lc and rc:\n",
    "                res = root\n",
    "                return True\n",
    "            if root is p or root is q:\n",
    "                return True\n",
    "            if lc or rc:\n",
    "                return True\n",
    "            return False\n",
    "            \n",
    "        isContain(root)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(\n",
    "        self, root: TreeNode, p: TreeNode, q: TreeNode\n",
    "    ) -> TreeNode:\n",
    "        if not root or root == p or root == q:\n",
    "            return root\n",
    "        l = self.lowestCommonAncestor(root.left, p, q)\n",
    "        r = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if l and r:\n",
    "            return root\n",
    "        return l or r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if root is None or root is p or root is q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right:\n",
    "            return root\n",
    "        if left:\n",
    "            return left\n",
    "        return right\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        res = None\n",
    "        def suforder(node):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "\n",
    "            left_p, left_q = suforder(node.left)\n",
    "            right_p, right_q = suforder(node.right)\n",
    "            cur_p, cur_q = 0, 0\n",
    "            if node == p:\n",
    "                cur_p = 1\n",
    "            if node == q:\n",
    "                cur_q = 1\n",
    "            \n",
    "            if ((left_q or right_q) and cur_p) or ((left_p or right_p) and cur_q) and not res:\n",
    "                res = node\n",
    "            if (left_p or right_p) and (left_q or right_q) and not res:\n",
    "                res = node\n",
    "            return (cur_p or left_p or right_p), (cur_q or left_q or right_q)\n",
    "        \n",
    "        suforder(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        # 0 都没有， 1有p, 2,有q, 3有pq\n",
    "        def search(node):\n",
    "            if node is None:\n",
    "                return 0, node\n",
    "            \n",
    "            left_s, left_n = search(node.left)\n",
    "            right_s, right_n = search(node.right)\n",
    "            \n",
    "            if left_s == 3:\n",
    "                return 3, left_n\n",
    "            elif right_s == 3:\n",
    "                return 3, right_n\n",
    "            elif (left_s == 1 and right_s == 2) or (left_s == 2 and right_s == 1):\n",
    "                return 3, node\n",
    "            elif ((left_s == 1 or right_s == 1) and (node.val == q.val)) or ((left_s == 2 or right_s == 2) and (node.val == p.val)) :\n",
    "                return 3, node\n",
    "            # elif (left_s == 2 or right_s == 2) and (node.val == p.val):\n",
    "            #     return 3, node\n",
    "            elif (left_s == 1 and right_s == 0) or (left_s == 0 and right_s == 1) or (node.val == p.val):\n",
    "                return 1, node\n",
    "            elif (left_s == 2 and right_s == 0) or (left_s == 0 and right_s == 2) or (node.val == q.val):\n",
    "                return 2, node\n",
    "            else:\n",
    "                return 0, node\n",
    "        s, n = search(root)\n",
    "        # print(s, n.val)\n",
    "        return n\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if root == None or root == p or root == q: return root\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        if left and right: return root\n",
    "        elif not left and right: return right\n",
    "        elif left and not right: return left\n",
    "        return \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        ancestors1 = []\n",
    "        hasfind1 = [False]\n",
    "        ancestors2 = []\n",
    "        hasfind2 = [False]\n",
    "        def helper(node, p, ancestors, hasfind):\n",
    "            if not node:\n",
    "                return\n",
    "            ancestors.append(node) # 双亲路径\n",
    "            if node == p:\n",
    "                hasfind[0] = True\n",
    "                return\n",
    "            if not hasfind[0]:\n",
    "                helper(node.left, p, ancestors, hasfind)\n",
    "            if not hasfind[0]:   \n",
    "                helper(node.right, p, ancestors, hasfind)\n",
    "            if not hasfind[0]:\n",
    "                popv = ancestors.pop()         \n",
    "        helper(root, p, ancestors1, hasfind1)\n",
    "        helper(root, q, ancestors2, hasfind2)\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        while p1 < len(ancestors1) and p2 < len(ancestors2):\n",
    "            if ancestors1[p1] != ancestors2[p2]:\n",
    "                break\n",
    "            else:\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "        if p1 < p2:\n",
    "            return ancestors1[p1-1]\n",
    "        else:\n",
    "            return ancestors2[p2-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.ans = None\n",
    "        def dfs(tree, n1, n2):\n",
    "            if not tree:\n",
    "                return False\n",
    "            lson = dfs(tree.left, n1, n2)\n",
    "            rson = dfs(tree.right, n1, n2)\n",
    "            if (lson and rson) or ((tree == p or tree == q) and (lson or rson)):\n",
    "                self.ans = tree\n",
    "            return (lson or rson or tree.val==p.val or tree.val==q.val)\n",
    "        dfs(root, p, q)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        #若根结点满足空，目标结点，则返回\n",
    "        if root in (None, p, q):\n",
    "            return root\n",
    "        #向左右子树寻找\n",
    "        left = self.lowestCommonAncestor(root.left, p, q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        #判断左右子树情况，两个均不为空，则返回当前结点\n",
    "        if left and right:\n",
    "            return root\n",
    "        #某个子树为空，返回另一个子树结点\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        trace_p, trace_q = [], []\n",
    "        def dfs(node, val, trace):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val == val:\n",
    "                trace.append(val)\n",
    "                return True\n",
    "            if dfs(node.left, val, trace):\n",
    "                trace.append(node.val)\n",
    "                return True\n",
    "            if dfs(node.right, val, trace):\n",
    "                trace.append(node.val)\n",
    "                return True\n",
    "            return False\n",
    "            \n",
    "        dfs(root, p.val, trace_p)\n",
    "        dfs(root, q.val, trace_q)\n",
    "        common_fa = set(trace_p) & set(trace_q)\n",
    "        # print(common_fa)\n",
    "        ans = inf\n",
    "        for fa in common_fa:\n",
    "            idx = trace_p.index(fa)\n",
    "            if idx < ans:\n",
    "                ans = idx\n",
    "        val = trace_p[ans]\n",
    "        # print(trace_p)\n",
    "        # print(trace_q)\n",
    "        res = None\n",
    "        def find(node, target_val):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return \n",
    "            if node.val == target_val:\n",
    "                res = node\n",
    "                return \n",
    "            find(node.left, target_val)\n",
    "            find(node.right, target_val)\n",
    "        # print(val)\n",
    "        find(root, val)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(root, p, q, ans):\n",
    "            if root is None:\n",
    "                return False\n",
    "            lson = dfs(root.left, p, q, ans)\n",
    "            rson = dfs(root.right, p, q, ans)\n",
    "            if (lson and rson) or ((root == p or root == q) and (lson or rson)):\n",
    "                ans.append(root)\n",
    "            return lson or rson or (root == p or root == q)\n",
    "\n",
    "        if root is None or root == p or root == q:\n",
    "            return root\n",
    "        ans = []\n",
    "        dfs(root, p, q, ans)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(root, p, q):\n",
    "            if root is None:\n",
    "                return False, None\n",
    "            hit_left, res_left = dfs(root.left, p, q)\n",
    "            hit_right, res_right = dfs(root.right, p, q)\n",
    "            if res_left is not None:\n",
    "                return True, res_left\n",
    "            elif res_right is not None:\n",
    "                return True, res_right\n",
    "            elif hit_left and hit_right:\n",
    "                return True, root\n",
    "            elif (hit_left or hit_right) and (root.val == p.val or root.val == q.val):\n",
    "                return True, root\n",
    "            elif hit_left or hit_right or (root.val == p.val or root.val == q.val):\n",
    "                return True, None\n",
    "            return False, None\n",
    "        hit, res = dfs(root, p, q)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        if root is p or root is q:\n",
    "            return root\n",
    "        left = self.lowestCommonAncestor(root.left, p,q)\n",
    "        right = self.lowestCommonAncestor(root.right, p, q)\n",
    "        left_is_goal = left is p or left is q\n",
    "        right_is_goal = right is p or right is q\n",
    "        if  left_is_goal and right_is_goal:\n",
    "            return root\n",
    "        elif left_is_goal:\n",
    "            return left\n",
    "        elif right_is_goal:\n",
    "            return right\n",
    "        else:\n",
    "            if left is not None:\n",
    "                return left\n",
    "            elif right is not None:\n",
    "                return right\n",
    "            else:\n",
    "                return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def f(root, p, q):\n",
    "            if not root: return 0\n",
    "            if root.val in d: return d[root.val]\n",
    "            res = 0\n",
    "            if root.val == p.val:\n",
    "                res |= 1\n",
    "            if root.val == q.val:\n",
    "                res |= 2\n",
    "            res |= f(root.left, p, q)\n",
    "            res |= f(root.right, p, q)\n",
    "            d[root.val] = res\n",
    "            return res\n",
    "        d = {}\n",
    "        def g(root):\n",
    "            if f(root, p, q) == 3:\n",
    "                if f(root.left, p, q) < 3 and f(root.right, p, q) < 3:\n",
    "                    return root\n",
    "                else:\n",
    "                    return g(root.left) or g(root.right)\n",
    "            return None\n",
    "        return g(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.res = None\n",
    "\n",
    "        def dfs(root = root):\n",
    "            if not root:\n",
    "                return\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "\n",
    "            if (left and right) or ((root==p or root==q) and (right or left)):\n",
    "                self.res = root\n",
    "\n",
    "            return root==p or root==q or left or right\n",
    "        \n",
    "        dfs()\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(root, p, q, ans):\n",
    "            if root is None:\n",
    "                return False\n",
    "            lson = dfs(root.left, p, q, ans)\n",
    "            rson = dfs(root.right, p, q, ans)\n",
    "            if (lson and rson) or ((root == p or root == q) and (lson or rson)):\n",
    "                ans.append(root)\n",
    "            return lson or rson or (root == p or root == q)\n",
    "\n",
    "        if root is None or root == p or root == q:\n",
    "            return root\n",
    "        ans = []\n",
    "        dfs(root, p, q, ans)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def find_ancestor(node):\n",
    "            if not node:\n",
    "                return False, False, None\n",
    "            l_p, l_q, l_n = find_ancestor(node.left)\n",
    "            if l_n:\n",
    "                return True, True, l_n\n",
    "            r_p, r_q, r_n = find_ancestor(node.right)\n",
    "            if r_n:\n",
    "                return True, True, r_n\n",
    "            c_p = node == p or l_p or r_p\n",
    "            c_q = node == q or l_q or r_q\n",
    "            return c_p, c_q, node if c_p and c_q else None\n",
    "\n",
    "        return find_ancestor(root)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(root, p, q, ans):\n",
    "            if root is None:\n",
    "                return False\n",
    "            lson = dfs(root.left, p, q, ans)\n",
    "            rson = dfs(root.right, p, q, ans)\n",
    "            if (lson and rson) or ((root == p or root == q) and (lson or rson)):\n",
    "                ans.append(root)\n",
    "            return lson or rson or (root == p or root == q)\n",
    "\n",
    "        if root is None or root == p or root == q:\n",
    "            return root\n",
    "        ans = []\n",
    "        dfs(root, p, q, ans)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def dfs(root,p,q):\n",
    "            left, right = None, None\n",
    "            if root.left:\n",
    "                left = dfs(root.left,p,q)\n",
    "            if root.right:\n",
    "                right = dfs(root.right,p,q)\n",
    "            print(root.val,left,right)\n",
    "            if left and right:\n",
    "                self.res = root\n",
    "                return None\n",
    "            elif (left or right) and (root.val == p.val or root.val == q.val):\n",
    "                self.res = root\n",
    "                return None\n",
    "            elif (left or right) and (root.val != p.val and root.val != q.val):\n",
    "                return True\n",
    "            elif (not left and not right) and (root.val == p.val or root.val == q.val):\n",
    "                return True\n",
    "            \n",
    "\n",
    "        self.res = None\n",
    "        dfs(root,p,q)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "\n",
    "        def search(root :TreeNode):\n",
    "     \n",
    "            if root:\n",
    "                a, a1, a2 = search(root.left)\n",
    "                if a:\n",
    "                    return a, a1, a2\n",
    "                b, b1, b2 = search(root.right)\n",
    "                if b:\n",
    "                    return b, b1, b2\n",
    "\n",
    "                a3 = (a1 or b1)\n",
    "                b3 = (a2 or b2)\n",
    "                if root == p and b3:\n",
    "                    return root, True, True\n",
    "                elif root == q and a3:\n",
    "                    return root, True, True\n",
    "                elif a3 and b3:\n",
    "                    return root, True, True\n",
    "                \n",
    "\n",
    "                if root == p:\n",
    "                    a3 = True\n",
    "                elif root == q:\n",
    "                    b3 = True\n",
    "\n",
    "                return None, a3, b3\n",
    "            else:\n",
    "                return None, False, False\n",
    "\n",
    "        return search(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        \n",
    "        self.res = None\n",
    "\n",
    "        def dfs(root = root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "\n",
    "            if (left and right) or ((root==p or root==q) and (right or left)):\n",
    "                self.res = root\n",
    "\n",
    "            return (True if root==p or root==q else False) or left or right\n",
    "        \n",
    "        dfs()\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        self.ans = None\n",
    "        self.flag = True\n",
    "        def dfs(root: TreeNode, target: TreeNode, path: [TreeNode]):\n",
    "            if root and self.flag:\n",
    "                path.append(root)\n",
    "                if root.val == target.val:\n",
    "                    self.ans = path.copy()\n",
    "                    self.flag = False\n",
    "                    return\n",
    "                else:\n",
    "                    dfs(root.left, target, path)\n",
    "                    dfs(root.right, target, path)\n",
    "                path.pop()\n",
    "        dfs(root, p, [])\n",
    "        path_p = self.ans\n",
    "        self.flag = True\n",
    "        dfs(root, q, [])\n",
    "        path_q = self.ans\n",
    "        for node in path_p[::-1]:\n",
    "            if node in path_q:\n",
    "                return node\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        \n",
    "        self.res = None\n",
    "\n",
    "        def dfs(root = root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "\n",
    "            if (left and right) or ((root==p or root==q) and (right or left)):\n",
    "                self.res = root\n",
    "\n",
    "            return (root==p or root==q) or left or right\n",
    "        \n",
    "        dfs()\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:\n",
    "        def find(root,l,r):\n",
    "            if not root:\n",
    "                return False, None\n",
    "            if p == root and q == root:\n",
    "                return True, root\n",
    "            fl, rl = find(root.left,l,r)\n",
    "            fr, rr = find(root.right,l,r)\n",
    "            if rl:\n",
    "                return True,rl\n",
    "            if rr:\n",
    "                return True,rr\n",
    "            flag = False\n",
    "            if root == p or root == q:\n",
    "                flag = True\n",
    "            if (fl and fr) or (fl and flag) or (fr and flag):\n",
    "                return True,root\n",
    "            return (flag or fl or fr), None\n",
    "        _,res = find(root,p,q)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
